package leetcode_classic150;

import model.ListNode;
import model.TreeNode;

import java.util.ArrayList;
import java.util.*;


class Node2 {
    public int val;
    public List<Node2> neighbors;
    public Node2() {
        val = 0;
        neighbors = new ArrayList<Node2>();
    }
    public Node2(int _val) {
        val = _val;
        neighbors = new ArrayList<Node2>();
    }
    public Node2(int _val, ArrayList<Node2> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}



public class Demo2 {

    // 205. 同构字符串
    public boolean isIsomorphic(String s, String t) {
        char[] hash = new char[128];
        boolean[] flag = new boolean[128];
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (hash[c1] != 0) {
                if (hash[c1] != c2) return false;
            } else {
                if(flag[c2]) return false;
                hash[c1] = c2;
                flag[c2] = true;
            }
        }
        return true;
    }



    // 86. 分隔链表
    public ListNode partition(ListNode head, int x) {
        ListNode newHead = new ListNode(), tmpHead = new ListNode();
        ListNode tail = newHead, tmpTail = tmpHead;

        for(ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val < x) {
                tail.next = cur;
                tail = tail.next;
            } else {
                tmpTail.next = cur;
                tmpTail = tmpTail.next;
            }
        }
        tail.next = tmpHead.next;
        tmpTail.next = null;
        return newHead.next;
    }


    // 129. 求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return postDfs(root, 0);
    }

    private int postDfs(TreeNode root, int val) {
        if (root == null) return val;
        val = val * 10 + root.val;

        if (root.left == null && root.right == null) return val;
        if (root.left == null) return postDfs(root.right, val);
        if (root.right == null) return postDfs(root.left, val);
        return postDfs(root.left, val)  + postDfs(root.right, val);
    }



    // 173. 二叉搜索树迭代器
    class BSTIterator {
        List<Integer> iterator;
        int cur;
        public BSTIterator(TreeNode root) {
            iterator = new ArrayList<>();
            cur = -1;
            inOrder(root);
        }

        public int next() {
            return iterator.get(++cur);
        }

        public boolean hasNext() {
            return cur < iterator.size() - 1;
        }
        private void inOrder(TreeNode root) {
            if (root == null) return;
            inOrder(root.left);
            iterator.add(root.val);
            inOrder(root.right);
        }
    }


    // 133. 克隆图
    public Node2 cloneGraph(Node2 node) {
        if (node == null) return null;

        // 使用Map记录每个结点的映射关系
        Map<Node2,Node2> hash = new HashMap<>();
        Queue<Node2> q = new LinkedList<>();
        hash.put(node, new Node2(node.val, new ArrayList<Node2>()));
        q.offer(node);

        while (!q.isEmpty()) {
            Node2 front = q.poll();
            for (Node2 tmp : front.neighbors) {
                if(!hash.containsKey(tmp)) {
                    q.offer(tmp);
                    hash.put(tmp, new Node2(tmp.val, new ArrayList<Node2>()));
                }
                hash.get(front).neighbors.add(hash.get(tmp));
            }
        }

        return hash.get(node);
    }




    // 2671. 频率跟踪器
    class FrequencyTracker {
        int[] nums;
        Map<Integer, Integer> hash;

        public FrequencyTracker() {
            nums = new int[100001];
            hash = new HashMap();
        }

        public void add(int number) {
            if (nums[number] > 0) {
                hash.put(nums[number], hash.get(nums[number]) - 1);
            }
            nums[number]++;
            hash.put(nums[number], hash.getOrDefault(nums[number], 0) + 1);
        }

        public void deleteOne(int number) {
            if (nums[number] > 0) {
                hash.put(nums[number], hash.get(nums[number]) - 1);
                nums[number]--;
            }
            if (nums[number] > 0) {
                hash.put(nums[number], hash.get(nums[number]) + 1);
            }
        }

        public boolean hasFrequency(int frequency) {
            return hash.containsKey(frequency) && hash.get(frequency) > 0;
        }
    }


    // 210. 课程表 II
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 1. 遍历 prerequisites 数组，得到各节点的入度和出度
        // 入度用 int[] 数组统计， 出度用 Map<Integer,List<Integer>> 统计
        int[] count = new int[numCourses];
        Map<Integer,List<Integer>> hash = new HashMap<>();
        for (int[] arr : prerequisites) {
            count[arr[0]]++;
            if (!hash.containsKey(arr[1])) {
                hash.put(arr[1], new ArrayList<>());
            }
            hash.get(arr[1]).add(arr[0]);
        }

        // 2. 将入度为 0 的结点加入队列
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (count[i] == 0) q.offer(i);
        }

        // 3. 尝试进行拓扑排序
        List<Integer> list = new ArrayList<>();
        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                Integer course = q.poll();
                list.add(course);
                if (hash.containsKey(course)) {
                    for (Integer x : hash.get(course)) {
                        count[x]--;
                        if (count[x] == 0) q.offer(x);
                    }
                }
            }
        }

        if (list.size() != numCourses) return new int[0];
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) res[i] = list.get(i);
        return res;
    }



    // 290. 单词规律
    public boolean wordPattern(String pattern, String s) {
        String[] hash = new String[26];
        Set<String> set = new HashSet<>();

        int left = 0, right = 0, n = s.length(), i = 0;
        for ( ; i < pattern.length() && right < n; i++) {
            char ch = pattern.charAt(i);

            while (right < n && s.charAt(right) != ' ') right++;
            String str = s.substring(left, right);
            if (hash[ch - 'a'] == null) {
                if (set.contains(str)) return false;
                hash[ch - 'a'] = str;
                set.add(str);
            } else {
                if (!hash[ch - 'a'].equals(str)) return false;
            }
            left = right = right + 1;
        }
        return i == pattern.length() && right == n + 1;
    }



    // 22. 括号生成
    List<String> ret;
    StringBuilder path;

    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(n, 0, 0);
        return ret;
    }

    public void dfs(int n, int left, int right) {
        if(path.length() == 2 * n) {
            ret.add(path.toString());
            return;
        }

        // 添加右括号
        if(left > right) {
            path.append(')');
            dfs(n, left, right + 1);
            path.deleteCharAt(path.length() - 1);
        }
        if(left < n) {
            path.append('(');
            dfs(n, left + 1, right);
            path.deleteCharAt(path.length() - 1);
        }
    }


    // 25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        // 1. 得到需要翻转的组数
        int count = 0;
        for(ListNode cur = head; cur != null; cur = cur.next) count++;
        count /= k;

        // 2. 进行 count次翻转，每次翻转 k 个结点
        ListNode newHead = new ListNode();
        ListNode tail = newHead, cur = head;
        while(count-- > 0) {
            ListNode tmpHead = null, tmp = cur;
            for(int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = tmpHead;
                tmpHead = cur;
                cur = next;
            }
            tail.next = tmpHead;
            tail = tmp;
        }
        // 3. 处理不用翻转的剩余结点
        tail.next = cur;
        return newHead.next;
    }



    // 380. O(1) 时间插入、删除和获取随机元素
    class RandomizedSet {
        private Map<Integer,Integer> hash;  // key-index
        private final int[] nums;           // key
        private int k;                  // 记录有多少个元素
        private Random random;

        public RandomizedSet() {
            hash = new HashMap<>();
            nums = new int[200000];
            random = new Random();
        }

        public boolean insert(int val) {
            if (hash.containsKey(val)) return false;
            hash.put(val, k);
            nums[k++] = val;
            return true;
        }

        public boolean remove(int val) {
            if (!hash.containsKey(val)) return false;
            int index = hash.remove(val);  // 获取删除元素在数组中的下标
            nums[index] = nums[--k];

            // 判断删除元素是否为数组最后一个元素
            if (index != k) {
                hash.put(nums[k], index);
            }
            return true;
        }

        public int getRandom() {
            return nums[random.nextInt(k)];
        }
    }




    // 228. 汇总区间
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if(nums.length == 0) return res;
        int n = nums.length;

        for (int i = 0, j = 1; i < n; ) {
            StringBuilder tmp = new StringBuilder();
            tmp.append(Integer.toString(nums[i]));

            while(j < n && nums[j] - nums[j - 1] == 1) j++;
            if (j - i > 1) {
                tmp.append("->");
                tmp.append(Integer.toString(nums[j - 1]));
            }

            res.add(tmp.toString());
            i = j++;
        }
        return res;
    }




    // 71. 简化路径
    public static String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        char[] arr = path.toCharArray();

        for(int i = 0, n = arr.length; i < n; ) {
            if(arr[i] == '/') {
                while(i < n && arr[i] == '/') i++;
            } else {
                int count = 0, j = i;
                for (; j < n && arr[j] == '.'; j++) count++;
                if ((count == 1 || count == 2) && (j == n || arr[j] == '/')) {
                    if (count == 2 && !stack.empty()) {
                        stack.pop();
                    }
                    i = j;
                    continue;
                }

                // 为文件或目录
                while (j < n && arr[j] != '/') j++;
                stack.push("/" + new String(arr, i, j - i));
                i = j;
            }
        }

        Collections.reverse(stack);
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) res.append(stack.pop());
        return res.length() == 0 ? "/" : res.toString();
    }



    // 104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }


    // 114. 二叉树展开为链表
    private TreeNode prev;
    public void flatten(TreeNode root) {
        if (root == null) return;

        if (prev != null) prev.right = root;
        prev = root;

        TreeNode rightTree = root.right;
        flatten(root.left);
        root.left = null;
        flatten(rightTree);
    }


    // 238. 除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // dp1[i]:在 i 位置之前所有元素的乘积
        // dp2[i]:在 i 位置之后所有元素的乘积
        int[] dp1 = new int[n], dp2 = new int[n];
        dp1[0] = dp2[n - 1] = 1;
        for (int i = 1; i < n; i++) dp1[i] = dp1[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--) dp2[i] = dp2[i + 1] * nums[i + 1];

        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = dp1[i] * dp2[i];
        return res;
    }



    // 12. 整数转罗马数字
    public String intToRoman(int num) {
        String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

        StringBuilder ret = new StringBuilder();
        for (int i = 0; num > 0; ) {
            if (num >= nums[i]) {
                ret.append(strs[i]);
                num -= nums[i];
            } else {
                i++;
            }
        }
        return ret.toString();
    }



    // 58. 最后一个单词的长度
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1, res = 0;
        while (i >= 0 && s.charAt(i) == ' ') i--;
        while (i >= 0 && s.charAt(i--) != ' ') res++;
        return res;
    }



    // 14. 最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        int len = 201;
        for (String s : strs) len = Math.min(len, s.length());

        int start = 0, end = 0, n = strs.length;
        while (end < len) {
            char ch = strs[0].charAt(end);
            int i = 1;
            for (; i < n; i++)
                if (ch != strs[i].charAt(end)) break;
            if (i < n) break;
            end++;
        }
        return strs[0].substring(start, end);
    }



    // 151. 反转字符串中的单词
    public String reverseWords(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();
        char[] arr = new char[n];
        int k = 0, cur = n - 1;
        while (cur >= 0) {
            while (cur >= 0 && ss[cur] == ' ') cur--;  // 跳过空格
            if (cur >= 0 && k > 0) arr[k++] = ' ';     // arr不为空且接下来还有单词则添加空格
            while (cur >= 0 && ss[cur] != ' ') arr[k++] = ss[cur--];    //  逆置单词
        }

        for (int left = 0, right = 0; left < k; ) {
            while (right < k && arr[right] != ' ') right++;
            reverse(arr, left, right - 1);
            left = right = right + 1;
        }
        return new String(arr, 0, k);
    }
    private void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char tmp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = tmp;
        }
    }




    // 6. Z 字形变换
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        int n = s.length();
        StringBuilder[] lists = new StringBuilder[numRows];
        Arrays.setAll(lists, i -> new StringBuilder());

        int cur = 0, flag = -1;  // cur表示当前行数, flag表示移动方向
        for (char ch : s.toCharArray()) {
            lists[cur].append(ch);
            if (cur == 0 || cur == numRows - 1) flag = -flag;
            cur += flag;
        }

        StringBuilder res = new StringBuilder();
        for (StringBuilder tmp : lists) res.append(tmp);
        return res.toString();
    }



    // 28. 找出字符串中第一个匹配项的下标
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (n < m) return -1;

        for (int i = 0; i <= n - m; i++) {
            if (haystack.charAt(i) == needle.charAt(0)) {
                int x = i, y = 0;
                for (; y < m; x++, y++) {
                    if (haystack.charAt(x) != needle.charAt(y)) break;
                }
                if (y == m) return i;
            }
        }
        return -1;
    }



    // 134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        for (int i = 0; i < n; i++) {
            if (gas[i] - cost[i] < 0) continue;     // 不具备出发条件

            int rest = 0, step = 0;
            for (int j = i; step < n; j = (j + 1) % n) {
                rest += gas[j] - cost[j];
                if (rest < 0) break;
                step++;
            }
            if (step == n) return i;
            i += step;
        }
        return -1;
    }
}
